package j_UnionFind;

import java.util.Arrays;

public class UnionFind_try implements UF{
	//only for union() and find(); 集合的合并 和 查询指定编号所在的集合；
	//通过编号(也就是元素)进行操作；
	
	private int[] parent;
	private int[] rank;
	public UnionFind_try(int size) {
		this.parent = new int[size];
		this.rank = new int[size];
	
		for (int i = 0; i < parent.length; i++) {
			parent[i] = i;
		}
		
		Arrays.fill(rank, 1);
		
	}
	
	public int find(int id) {
		
		assert id>=0 && id<parent.length;
		
		while(id != parent[id]) {
			parent[id] = parent[parent[id]];
			id = parent[id];
		}
		
		return id;
	}
	
	public void union(int p, int q) {
		int rootP = find(p);
		int rootQ = find(q);
		
		if(rootP == rootQ)    //漏掉
			return;
		
		if(rank[rootP] > rank[rootQ])
			parent[rootQ] = parent[rootP]; 
		else if(rank[rootP] < rank[rootQ])
			parent[rootP] = parent[rootQ];
		else {
			parent[rootP] = parent[rootQ];
			rank[rootQ] ++;
		}
	}
	
	public boolean isConnected(int p, int q) {
		return find(p) == find(q);
	}
	
	public int getSize() {
		return parent.length;
	}
	
	@Override
	public String toString() {
		return super.toString();
	}
	
	public static void main(String[] args) {
	UnionFind_try uf= new UnionFind_try(22);
}

	@Override //方便测试，实现了一下接口，该方法等同于union();
	public void unionElements(int p, int q) {
		
		int rootP = find(p);
		int rootQ = find(q);
		
		if(rootP == rootQ)    //漏掉
			return;
		
		if(rank[rootP] > rank[rootQ])
			parent[rootQ] = parent[rootP]; 
		else if(rank[rootP] < rank[rootQ])
			parent[rootP] = parent[rootQ];
		else {
			parent[rootP] = parent[rootQ];
			rank[rootQ] ++;
		}
		
	}
}
